// https://www.lintcode.com/problem/subarray-sum-equals-k/

public class Solution {
    /**
     * @param nums: a list of integer
     * @param k: an integer
     * @return: return an integer, denote the number of continuous subarrays whose sum equals to k
     */
    public int subarraySumEqualsK(int[] nums, int k) {
        // write your code here
        // 遍历数组nums，计算从第0个元素到当前元素的和，用哈希表保存出现过的累积和sum的次数。
        // 如果sum - k在哈希表中出现过，则代表从当前下标i往前有连续的子数组的和为k！！！
        int ret = 0, sum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 0的情况必然出现过。
        for (int n : nums) {
            sum += n;
            if (map.containsKey(sum - k)) {
                ret += map.get(sum - k);
            }
            if (!map.containsKey(sum)) {
                map.put(sum, 0);
            }
            map.put(sum, map.get(sum) + 1);
        }
        return ret;
    }
}